1. Field of the Invention
The present invention generally relates to navigation and planning optimization systems and, more particularly, to route planning for travel paths subject to a variety of navigational constraints.
2. Description of the Prior Art
When a course of travel is not constrained by roads or other fixed structures, such as during travel by air or water or over unimproved land, careful navigation along a path extending from a starting point to a goal is required. The choice of a path may, in such a case, be constrained by many factors such as range or other physical limitations of a vehicle, weather conditions and other conditions which may compromise safety, and human factors, such as operator (e.g. pilot) workload. Some fixed structures may also affect the choice of path such as the orientation of a runway, the physical layout of harbors, docks and the like as well as physical obstacles which may be man-made or natural.
In the past, a trained navigator (generally a pilot, driver or ship officer, sometimes referred to collectively hereinafter as simply "pilot") would choose a path or course based on the best available information concerning as many of the above matters as possible. However, in practice, often information would be available concerning only a few of the above matters. While greater availability of information has improved safety and efficiency of route choice, even highly trained navigators are unable to assimilate the amount of information which may be available or to assign an appropriate degree of importance to each item of information and are thus able to perform only the most rudimentary of quantitative optimization of route details. Further, planning by a navigator including responses to changes of conditions or circumstances is always subject to human error; the likelihood of which increases with the amount of information available for consideration.
Additionally, in recent years, many more types of information and constraints have been included in route planning which further complicates the route planning process for a human navigator. Such constraints may include, but are not limited to, minimum leg length (e.g. a minimum interval in time or distance between changes of course) and maximum turning angle (e.g. a limit of the vehicle or an angle at which likelihood of collision is not significantly increased when plural vehicles are traversing the route in close proximity to one another). Accordingly, attempts have been made to use automated data processing to plan travel routes.
Known route planning or optimization techniques generally follow one of two distinct methodologies: grid-based techniques and graph-based techniques. Each of these categories has its own distinct advantages and disadvantages.
Grid-based techniques are generally directed to optimization to the level of grid cell resolution employed and can generally converge to a relatively accurate solution in real time. However, grid-based techniques can accommodate quantitative metrics and limits and particular constraints only with difficulty and a solution complying therewith may not be found. Further, discontinuities in the search space may not allow some solutions to be reliably found, particularly an alternate solution which may be preferable to an optimum solution but which may be altered therefrom to a seemingly slight degree.
Graph-based techniques are generally very accurate and can generally accommodate metrics and constraints but often suffer from long convergence times, if they converge to a solution at all, since they carry out an exhaustive search of the search space while concurrently applying constraints. Therefore, graph-based techniques require large computing resources if they are to support even the possibility that a solution may be found within a practical amount of time. On the other hand, even large computing resources cannot guarantee that a solution will be found within an acceptable amount of time. Moreover, the possibility of changing circumstances effectively reduces the acceptable time period for finding a solution to a travel problem.
Additionally, the mode of transportation may greatly affect the detail of the planning as well as the relative importance of circumstances in development of a route plan. For example, speed of a vehicle may determine the level of relevant detail and the minimum time or distance between turns. The nature of the mission and the number of vehicles involved as well as speed and maneuverability thereof may affect the maximum allowed turn angle, and so forth.
Accordingly, it has been determined by the inventors that a need has existed for an automated system for travel route planning which could be easily customized to the constraints imposed by the vehicle and other circumstances to produce, in real-time, a route which is as good or better than could be produced by a trained navigator.